package com.zhouyong.leetcode.链表的中间结点876;

import com.zhouyong.leetcode.ListNode;

/**
 * @Author 99
 * @Date 2022/9/30 16:21
 * @Version 1.0
 */
public class Test {

    // 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    // 内存消耗：38.8 MB, 在所有 Java 提交中击败了77.62%的用户

    // 输入：[1,2,3,4,5]
    // 输出：此列表中的结点 3 (序列化形式：[3,4,5])
    // 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
    // 注意，我们返回了一个 ListNode 类型的对象 ans，这样：
    // ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

    public static void main(String[] args) {
        ListNode node = new ListNode(0, new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null))))));
        System.out.println(middleNode(node));
    }

    public static ListNode middleNode(ListNode head) {

        // 较为简单的方法
//        ListNode[] a = new ListNode[100];
//        int count = 0;
//        while (head != null) {
//            a[count++] = head;
//            head = head.next;
//        }
//        return a[count / 2];

        // 写复杂了
//        ArrayList<ListNode> list = new ArrayList<>();
//        while (head != null) {
//            list.add(head);
//            head = head.next;
//        }
//        int middle = list.size() / 2;
//        ListNode ans = null;
//        for (int size = list.size() - 1; size >= middle; size--) {
//            ans = new ListNode(list.get(size).val, ans);
//        }
//        return ans;

        // 单指针法
        // 我们可以对方法一进行空间优化，省去数组 A。
        // 我们可以对链表进行两次遍历。第一次遍历时，我们统计链表中的元素个数 N；
        // 第二次遍历时，我们遍历到第 N/2 个元素（链表的首节点为第 0 个元素）时，将该元素返回即可。
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            ++n;
            cur = cur.next;
        }
        int k = 0;
        cur = head;
        while (k < n / 2) {
            ++k;
            cur = cur.next;
        }
        return cur;
    }
}
